package leetcode.D200.T105;

import util.TreeNode;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-09-27 23:13:29 星期一
 */
public class Solution {
    // 一刷
    /*public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length);
    }

    private TreeNode build(int[] preorder, int[] inorder, int prel, int prer, int inl, int inr) {
        if(prel > prer) {
            return null;
        }
        int k = inl;
        for(int i=inl; i<=inr; ++i) {
            if(inorder[i] == preorder[prel]) {
                k = i;
                break;
            }
        }
        TreeNode root = new TreeNode(preorder[prel]);
        root.left = build(preorder, inorder, prel+1, prel+k-inl, inl, k-1);
        root.right = build(preorder, inorder, prel+k-inl+1, prer, k+1, inr);
        return root;
    }*/

    // 二刷
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    private TreeNode buildTree(int[] preorder, int[] inorder, int prel, int prer, int inl, int inr) {
        if (prel > prer)
            return null;
        TreeNode root = new TreeNode(preorder[prel]);
        int k = 0;
        for (k = inl; k <= inr; ++k) {
            if (inorder[k] == root.val)
                break;
        }
        root.left = buildTree(preorder, inorder, prel+1, prel+k-inl, inl, k-1);
        root.right = buildTree(preorder, inorder, prel+k-inl+1, prer, k+1, inr);
        return root;
    }
}
